#include<iostream>
using namespace std;

// 最多皇后个数
#define MAXN 20

// 存放各皇后所在的列号, 为全局变量
int q[MAXN];	

// 累计解个数
int cnt = 0;

// 输出一个解
void disp(int n)
{
	printf("  第%d个解:",++cnt);
	for (int i=1;i<=n;i++)
		printf("(%d,%d) ",i,q[i]);
	printf("\n");
}

// 测试(i,j)位置能否摆放皇后
bool place(int i, int j)	
{
	// 第一个皇后总是可以放置
	if (i==1) return true;
	
	// k=1～i-1是已放置了皇后的行
	int k=1;
	while (k<i)
	{
		if ((q[k]==j) || (abs(q[k]-j)==abs(i-k)))
			return false;
		k++;
	}
	return true;
}

// 递归解法
void queen11(int n, int i)
{
	// 所有皇后放置结束
	if (i > n)
		disp(n);	
	
	// 皇后未放置结束
	else
	{
		// 在第i行上试探每一个列j
		for (int j=1; j<=n; j++)
			if (place(i, j)) // 在第i行上找到一个合适位置(i, j)
			{
				q[i] = j;
				queen11(n, i+1);
				q[i] = 0; // 回溯
			}
	}
}

// 递归法求解n皇后问题
void queen1(int n)
{
	queen11(n, 1);
} 

// 迭代解法
void queen2(int n)
{
	// i表示当前行,也表示放置第i个皇后
	int i=1;	
	
	// q[i]是当前列,从0列即开头试探
	q[i]=0;
	
	// 重复试探
	while (i >= 1)
	{
		q[i]++;
		
		// 试探一个位置(i, q[i])
		while (q[i]<=n && !place(i, q[i]))
			q[i]++;
		
		// 为第i个皇后找到了一个合适位置(i, q[i])
		if (q[i] <= n)
		{
			// 若放置了所有皇后,输出一个解
			if (i==n)
				disp(n);
			
			// 皇后没有放置完
			else
			{
				// 转向下一行,即开始下一个皇后的放置
				i++;	
				
				// 每次放一个新皇后,都从该行的列头进行试探
				q[i]=0;
			}
		}
		
		// 若第i个皇后找不到合适的位置,则回溯到上一个皇后
		else i--;
	}
}

int main()
{
	// n存放实际皇后个数
	int n = 6;
	printf("%d皇后问题求解如下:\n", n);
	
	// 求解n皇后问题
	queen1(n);
	return 0;
}
